﻿// Sequin.Sequences.Mining.ClosedSequenceMiner
//
// (c) 2011 Arthur Pitman
//
// Part of the Sequin Library
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License (Version 2.1) as published by the Free Software Foundation.
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License (Version 2.1) along with this library; if not, write to the 
// Free Software Foundation, Inc., 
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
// or see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sequin.Sequences.Mining
{
	/// <summary>
	/// Closed sequence mining based on the BIDE algorithm (Wang, Han and Li)
	/// </summary>
	public class ClosedSequenceMiner : SequenceMiner
	{
		/// <summary>
		/// Optional observer of mining events
		/// </summary>
		protected IClosedSequenceMinerObserver closedSequenceMinerObserver;

		/// <summary>
		/// Initializes a new instance of the <see cref="ClosedSequenceMiner"/> class
		/// </summary>
		/// <param name="maximumThreadCount">Maximum number of threads</param>
		/// <param name="maximumForkDepth">Maximum depth at which forking can occur</param>
		/// <param name="sequenceMinerObserver">Optional observer of mining events</param>
		public ClosedSequenceMiner(int maximumThreadCount, int maximumForkDepth, ISequenceMinerObserver sequenceMinerObserver = null)
			: base(maximumThreadCount, maximumForkDepth,  sequenceMinerObserver)
		{
			if (sequenceMinerObserver is IClosedSequenceMinerObserver)
				this.closedSequenceMinerObserver = (IClosedSequenceMinerObserver)sequenceMinerObserver;
		}

		/// <summary>
		/// Decides if a projection should be expanded
		/// This method implements back scan pruning as defined in the BIDE algorithm
		/// </summary>
		/// <param name="projection">The <see cref="Projection"/> to consider</param>
		/// <returns><c>true</c> if the projection should be expanded</returns>
		protected override bool ShouldExpandProjection(Projection projection)
		{
			// root projection should always be expanded
			if (projection.Depth == 0)
				return true;

			HashSet<int>[] backscanIExtensions = null;
			HashSet<int>[] backscanSExtensions = null;			

			// if no backscan extension exists, the projection must be expanded
			if (!FindBackscanExtensions(projection, out backscanIExtensions, out backscanSExtensions))
				return true;

			// otherwise it may be pruned
			if (closedSequenceMinerObserver != null)
				closedSequenceMinerObserver.OnBackscanExtension(projection);
			return false;
		}

		/// <summary>
		/// Finds all possible backscan extensions
		/// </summary>
		/// <param name="projection">The <see cref="Projection"/> to consider</param>
		/// <param name="backscanIExtensions">Receives possible backscan item extensions</param>
		/// <param name="backscanSExtensions">Receives possible backscan sequence extensions</param>
		/// <returns><c>true</c> if a backscan extension exists otherwise <c>false</c></returns>
		protected bool FindBackscanExtensions(Projection projection, out HashSet<int>[] backscanIExtensions, out HashSet<int>[] backscanSExtensions)
		{
			var projectingSequenceRaw = projection.ProjectingSequence.Value;
			
			backscanIExtensions = new HashSet<int>[projectingSequenceRaw.Length];
			backscanSExtensions = new HashSet<int>[projectingSequenceRaw.Length];

			bool isFirst = true;
			foreach (var projectedSequence in projection.ProjectedDb)
			{
				var sequenceRaw = projectedSequence.Seq.Value;

				int[] prefixPoints = new int[projectingSequenceRaw.Length];
				int[] lastInFirstPoints = new int[projectingSequenceRaw.Length];

				// IDEA: find n-th last-in-first appearance first (then work backwards)
				// NOTE: assume that the sequence supports the pattern!!

				// start by finding n-th first-in-first
				// along the way, find all prefix points (first-in-first)
				int pIndex = 0;
				int sIndex = 0;
				while ((pIndex < projectingSequenceRaw.Length) && (sIndex < sequenceRaw.Length))
				{
					if (Sequence.ElementContains(sequenceRaw[sIndex], projectingSequenceRaw[pIndex]))
					{
						prefixPoints[pIndex] = sIndex;
						pIndex++;
					}
					sIndex++;
				}

				int lastLastInFirst = sIndex - 1;
				pIndex--;
				lastInFirstPoints[pIndex] = lastLastInFirst;
				pIndex--;
				if (pIndex >= 0)
				{
					// go backwards to find the others
					sIndex = lastLastInFirst - 1;
					for (; sIndex >= 0; sIndex--)
					{
						if (Sequence.ElementContains(sequenceRaw[sIndex], projectingSequenceRaw[pIndex]))
						{
							lastInFirstPoints[pIndex] = sIndex;
							pIndex--;
							if (pIndex == -1)
								break;
						}
					}
				}

				// examine all semi-maximum periods
				bool validExtensionExists = false;
				int startPoint = 0;
				int lastP = projectingSequenceRaw.Length - 1;
				int lastItemInPattern = projectingSequenceRaw[lastP].Last();
				for (int p = 0; p < projectingSequenceRaw.Length; p++)
				{
					var existingSSet = backscanSExtensions[p];
					if (isFirst || (existingSSet != null))
					{
						var newSSet = new HashSet<int>();
						for (int si = startPoint; si <= lastInFirstPoints[p]; si++)
						{
							if (si < lastInFirstPoints[p])
							{
								foreach (var item in sequenceRaw[si])
								{
									if (isFirst || existingSSet.Contains(item))
									{
										newSSet.Add(item);
										validExtensionExists = true;
									}
								}
							}
						}

						if (isFirst || (existingSSet != null))
							backscanSExtensions[p] = newSSet;
					}
					startPoint = prefixPoints[p] + 1;
				}

				// NEW I pruning implementation to fix flaws in original BIDE					
				for (int p = 0; p < projectingSequenceRaw.Length; p++)
				{
					var existingISet = backscanIExtensions[p];
					if (isFirst || (existingISet != null))
					{

						int lastItemInElement = projectingSequenceRaw[p].Last();
						int elementInstanceCount = 0;
						Dictionary<int, int> itemFrequencyTable = new Dictionary<int, int>();
						for (int i = 0; i < sequenceRaw.Length; i++)
						{
							int[] projectedItems = null;
							if (Sequence.ProjectElement(sequenceRaw[i], projectingSequenceRaw[p], out projectedItems))
							{
								elementInstanceCount++;
								foreach (var item in projectedItems)
								{
									if ((p == lastP) && (item >= lastItemInPattern))
										continue;
									if (itemFrequencyTable.ContainsKey(item))
										itemFrequencyTable[item]++;
									else
										itemFrequencyTable.Add(item, 1);
								}
							}
						}

						var newISet = new HashSet<int>();
						var applicableItems = from x in itemFrequencyTable
											  where x.Value == elementInstanceCount
											  select x.Key;
						foreach (var item in applicableItems)
						{
							if (isFirst || existingISet.Contains(item))
							{
								newISet.Add(item);
								validExtensionExists = true;
							}
						}
						if (isFirst || (existingISet != null))
							backscanIExtensions[p] = newISet;
					}
				}

				if (!validExtensionExists)
					return false;

				isFirst = false;
			}
			return true;
		}

		/// <summary>
		/// Decides if a sequential pattern should be emitted for the projection
		/// Checks for forward or backward extensions as per BIDE algorithm
		/// </summary>
		/// <param name="projection">The <see cref="Projection"/> to consider</param>
		/// <param name="validIExtensionProjections">Item extensions</param>
		/// <param name="validSExtensionProjections">Sequence extensions</param>
		/// <returns><c>true</c> if a sequential pattern should be emitted</returns>
		protected override bool ShouldEmitPattern(Projection projection, IEnumerable<Projection> validIExtensionProjections, IEnumerable<Projection> validSExtensionProjections)
		{
			// check for a forward extension
			List<int> forwardIExtensions = null;
			List<int> forwardSExtensions = null;
			if (FindForwardExtensions(projection, validIExtensionProjections, validSExtensionProjections, out forwardIExtensions, out forwardSExtensions))
			{
				if (closedSequenceMinerObserver != null)
					closedSequenceMinerObserver.OnForwardExtension(projection);
				return false;
			}
					
			// no backward extension exists for empty sequence --> closed
			if (projection.Depth == 0)
				return true;

			// check for a backwards extension
			HashSet<int>[] backwardIExtensions = null;
			HashSet<int>[] backwardSExtensions = null;

			// if no forward or backward extensions is found, the sequential pattern must be emitted
			if (!FindBackwardExtensions(projection, out backwardIExtensions, out backwardSExtensions))
				return true;

			// a backwards extension with the same support was found --> not closed
			if (closedSequenceMinerObserver != null)
				closedSequenceMinerObserver.OnBackwardExtension(projection);

			return false;
		}

		/// <summary>
		/// Finds all possible forward extensions
		/// </summary>
		/// <param name="projection">The <see cref="Projection"/> to consider</param>
		/// <param name="validIExtensionProjections">Item extensions</param>
		/// <param name="validSExtensionProjections">Sequence extensions</param>
		/// <param name="forwardIExtensions">Receives possible forward item extensions</param>
		/// <param name="forwardSExtensions">Receives possible forward sequence extensions</param>
		/// <returns><c>true</c> if a forward extension exists otherwise <c>false</c></returns>
		protected bool FindForwardExtensions(Projection projection, IEnumerable<Projection> validIExtensionProjections, IEnumerable<Projection> validSExtensionProjections, out List<int> forwardIExtensions, out List<int> forwardSExtensions)
		{
			bool foundForwardExtension = false;
			forwardSExtensions = new List<int>();
			forwardIExtensions = new List<int>();

			var currentSupportCount = projection.ProjectedDb.Count;
			foreach (var childProjection in validIExtensionProjections)
			{
				if (childProjection.ProjectedDb.Count == currentSupportCount)
				{
					forwardIExtensions.Add(childProjection.ProjectingSequence.GetLastItemInLastElement());
					foundForwardExtension = true;
				}
			}
			foreach (var childProjection in validSExtensionProjections)
			{
				if (childProjection.ProjectedDb.Count == currentSupportCount)
				{
					forwardSExtensions.Add(childProjection.ProjectingSequence.GetLastItemInLastElement());
					foundForwardExtension = true;
				}
			}
			return foundForwardExtension;
		}
	
		/// <summary>
		/// Find all possible backward extensions
		/// </summary>
		/// <param name="projection">The <see cref="Projection"/> to consider</param>
		/// <param name="backwardIExtensions">Receives possible backward item extensions</param>
		/// <param name="backwardSExtensions">Receives possible backward sequence extensions</param>
		/// <returns>><c>true</c> if a backward extension exists otherwise <c>false</c></returns>
		protected bool FindBackwardExtensions(Projection projection, out HashSet<int>[] backwardIExtensions, out HashSet<int>[] backwardSExtensions)
		{					
			var projectingSequenceRaw = projection.ProjectingSequence.Value;						
			backwardIExtensions = new HashSet<int>[projectingSequenceRaw.Length];
			backwardSExtensions = new HashSet<int>[projectingSequenceRaw.Length];

			bool isFirst = true;
			foreach (var projectedSequence in projection.ProjectedDb)
			{
				var sequenceRaw = projectedSequence.Seq.Value;

				// find the last in last points by working through the sequence backwards
				int[] lastInLastPoints = new int[projectingSequenceRaw.Length];
				int pIndex = projectingSequenceRaw.Length - 1;
				for (int sIndex = sequenceRaw.Length - 1; sIndex >= 0; sIndex--)
				{
					if (Sequence.ElementContains(sequenceRaw[sIndex], projectingSequenceRaw[pIndex]))
					{
						lastInLastPoints[pIndex] = sIndex;
						pIndex--;
						if (pIndex == -1)
							break;
					}
				}

				// find the prefix points
				int[] prefixPoints = new int[projectingSequenceRaw.Length];
				pIndex = 0;
				for (int sIndex = 0; sIndex < sequenceRaw.Length; sIndex++)
				{
					if (Sequence.ElementContains(sequenceRaw[sIndex], projectingSequenceRaw[pIndex]))
					{
						prefixPoints[pIndex] = sIndex;
						pIndex++;
						if (pIndex == projectingSequenceRaw.Length)
							break;
					}
				}

				// examine all maximum periods for backwards S frequencies
				bool validExtensionExists = false;
				int startPoint = 0;
				int lastP = projectingSequenceRaw.Length - 1;
				int lastItemInPattern = projectingSequenceRaw[lastP].Last();
				for (int p = 0; p < projectingSequenceRaw.Length; p++)
				{
					if (isFirst || (backwardSExtensions[p] != null) || (backwardIExtensions[p] != null))
					{
						var existingISet = backwardIExtensions[p];
						var newISet = new HashSet<int>();

						var existingSSet = backwardSExtensions[p];
						var newSSet = new HashSet<int>();
						for (int si = startPoint; si <= lastInLastPoints[p]; si++)
						{
							if ((isFirst || (existingSSet != null)) && (si < lastInLastPoints[p]))
							{
								foreach (var item in sequenceRaw[si])
								{
									if (isFirst || existingSSet.Contains(item))
									{
										newSSet.Add(item);
										validExtensionExists = true;
									}
								}
							}

							if (isFirst || (existingISet != null))
							{
								int[] projectedItems = null;
								if (Sequence.ProjectElement(sequenceRaw[si], projectingSequenceRaw[p], out projectedItems))
								{
									foreach (var item in projectedItems)
									{
										if ((p == lastP) && (item >= lastItemInPattern))
											continue;

										if (isFirst || existingISet.Contains(item))
										{
											newISet.Add(item);
											validExtensionExists = true;
										}
									}
								}
							}
						}

						if (isFirst || (existingISet != null))
							backwardIExtensions[p] = newISet;

						if (isFirst || (existingSSet != null))
							backwardSExtensions[p] = newSSet;
					}
					startPoint = prefixPoints[p] + 1;
				}
				if (!validExtensionExists)
					return false;
				isFirst = false;
			}
			return true;
		}
		
	}
}
